The present invention relates to a verifiable anonymous channel which is used, for instance, to implement secret voting through an electrical communication system and, more particularly, to an anonymous channel that can be implemented with high efficiency.
To facilitate a better understanding of the present invention, a description will be given of an anonymous channel. In general, each server can identify users connected thereto, and hence it can recognize the correspondence between the users and the messages that they are sending; therefore, channels between the users and the server have no anonymity. MIX-NET has been proposed to implement an anonymous channel not by a physical configuration but in the form of an electrical communication system. MIX-NET is a system wherein L servers U1, . . . , UL are cascade-connected via non-anonymous channels.
In the case of implementing the system through the use of the RSA function, an i-th server uses, as a decryption and an encryption key, (di, ni) and (ei, ni) which satisfy ni=pi−qi and ei−di=1(mod LCM(pi−1, qi−1)) for large primes pi and qi, respectively. The encryption of a message m by RSA starts with the selection of a random number r, followed by concatenating m and r into m∥r and then by obtaining an encrypted message M as M:=(m∥r)gi mod ni. This encryption procedure using the encryption key (ei, ni) of the server U1 will hereinafter be denoted by Ei(m,r).
A j-th user uses encryption keys (ei, ni) of all servers, where i=1, 2, . . . , L, and L random numbers rj1, rj2, . . . , rjL, for multiple encryption of his message mj into
M1:=E1(E2( . . . (EL(mj, rjL), . . . ), rj2), rji)
and then sends the encrypted message M1 to the server U1.
Having received encrypted messages M1, M2, . . . from more than two users, the server U1 decrypts them with the key (di, ni) to obtain E2( . . . (EL(mj, rjL), . . . ), rj2) and rj1 corresponding to each message mj. The server U1 randomly permutes E2( . . . (EL(mj, rjL), . . . ), rj2), where j=1, 2, . . . , derived from the encrypted messages and sends them to the server U2. At this time, by making secret the random number rj1 attached to each message mj, the server U1 can cut the link between E2( . . . (EL(mj, rjL), . . . ), rj2) sent to the server U2 and the encrypted messages M1, M2, . . . input to the server U1.
The servers U2, . . . , UL also repeat the same processing as mentioned above. Finally, the server UL makes each message mj public. By making a secret of the random number rji and the order of permutation by at least one server Ui, the correspondence between the ciphertexts input into the server U1 and the messages output from the server UL is concealed; that is, the channel functions as an anonymous channel.
With the conventional scheme described above, even if each server does not perform a predetermined operation but falsifies or stealthily replaces messages, no one can detect the faults in of the output.
One possible scheme that provides verifiability is proposed, for example, in Masayuki ABE, “Universally Verifiable Mix-Net with Verification Work Independent of the Number of Mix-Servers,” EUROCRYPT98, May 31. According to the proposed scheme, servers perform randomization and permutation first and then mutually prove and verify their outputs. Then, they perform the decryption and also mutually prove and verify their decrypted outputs. This scheme has the disadvantage of a high computation cost for the proof and verification by each server. For example, in the permutation process, let O1, . . . , ON represent the results of the randomization and random permutation of inputs I1, . . . , IN. To prove, without revealing the random choices, that the outputs are the result of randomization and random permutation, the following steps are taken. The inputs I1, . . . , IN are randomized and randomly permuted; in the same way with independently chosen random factors, the results of process being represented by O′1, . . . , O′N. In this instance, due to the homomorphic property of the randomization, O′1, . . . , O′N can be regarded as the result of randomization of O1, . . . , ON. Here, the verifier chooses 0 or 1 as a challenge and sends it to the prover. When the challenge is 0, the prover publishes all the random choices used for the randomization/permutation of {I1, . . . , IN}→{O′1, . . . , O′N}. When the challenge is 1, the prover publishes its random choices used for the randomization of {O1, . . . , ON}→{O′1, . . . , O′N}. Once the random choices are known, the entire procedure can definitely be repeated, enabling the prover to verify the correctness of the input/output relationship. The probability that a fault by the prover in the above procedure cannot be detected is 1/2, equal to the probability that the prover guesses right the challenge; hence, the prover and the verifier repeat the above procedure a desired number k of times in order to prove and verify the correctness of the permutation/randomization process with an error probability (1/2)k. Accordingly, the overall efficiency for N inputs is linear in Nk. The security parameter k is typically set at 80 to provide high reliability of the system.
Though not described to be applied to the anonymous channel, another scheme for verification is set forth in R. Cramer, I. Damgard and B. Schoenmakers, “Proofs of Partial Knowledge and Simplified Design of Witness Hiding Proofs,” Proc. of Crypto '94, LNCS 839, pp. 174-187, Springer-Verlag. According to this scheme, the permutation of N inputs can be proved at a computation cost of N2 as described below in brief. Letting O1 represent the result of randomization of an input I1, the relationship between I1 and O1 can be proved using a zero-knowledge interactive proof without revealing random elements used for the randomization. To execute such a zero-knowledge interactive proof, the following steps are performed:
1. The prover sends to the verifier a random message T called a commitment;
2. The verifier sends to the prover a random value C called a challenge C; and
3. The prover sends to the verifier a value Z that satisfies a verification equation on the basis of the commitment T and the challenge C.
The verifier makes a check to see if (T, C, Z, I1, O1) satisfies a predetermined verification equation, thereby verifying the correctness of the relationship between I1 and O1. In such a proof system, if the prover does not know the value of the challenge C prior to the preparation of the commitment T, he can send the value Z that satisfies the verification equation only when the relationship between I1 and O1 is correct. On the other hand, however, if the prover knows the value C in advance, he can compute the values T and Z that satisfy the verification equation even if the relationship between I1 and O1 is not valid. Through utilization of this fact, it is possible for the prover to indicate that I1 bears a valid or correct relationship to any one or more of O1, . . . , ON. In the first place, the prover randomly selects C2, . . . , CN and Z2, . . . , ZN corresponding thereto, then determines the value of Ti such that (Ti, Ci, Zi, Ii, Oi) satisfies a predetermined verification equation for i=1, . . . , N. Furthermore, the prover chooses T1 randomly. Thereafter, the following steps are carried out.
1. The prover sends T1, . . . , TN to the verifier;
2. The verifier sends his randomly chosen C to the prover, and
3. The prover computes C1=C⊕C2⊕ . . . ⊕CN, then computes the value Z1 such that (T1, C1, Z1, I1, O1) satisfies a verification equation, and sends Z1, . . . , ZN and C1, . . . , CN to the verifier. Here, ⊕ means bitwise exclusive OR. The verifier needs only to verify that (Ti, Ci, Zi, Ii, Oi) satisfies a predetermined verification equation for all of i=1, . . . , N and to makes sure that C=C1⊕ . . . ⊕CN holds. Since the prover does not know the value C in advance, he cannot manipulate at least one value Ci inevitably; accordingly, it is possible to confirm that I1 bears a correct relation to at least one value Oi.
With this scheme, the computation and communication costs for proving the relation I1→O1 or . . . or ON are N times larger than those for proving the relation I1→O1, and consequently, the efficiency for proving the relation {O1, . . . , ON}→{O′1, . . . , O′N} is in the order of N2. Accordingly, an increase in the number N of inputs gives rise to a problem that the amount of data to be processed becomes enormous.
As described above, according to the conventional schemes, the computation and communication cost for the proof and verification by each server is proportional in Nk or N2, providing the disadvantage of low efficiency.